令 , 可以 预处理
注意到当 时函数值为0 , 的大部分值为 ,所以有贡献的情况不多。
对于 ,当 且 时连边。
可以枚举最大公因数 后枚举倍数 , 但要保证 。
这样图上的三元环便对应着每一种有贡献的情况。
最后特殊统计一下三个点相等和两个点相等的情况。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int Mod = 1e9 + 7 , MAXN = 1e5;
int t , A , B , C , n , m;
int cnt , vt[ MAXN + 5 ] , Deg[ MAXN + 5 ];
struct node {
int u , v , w;
}E[ 8 * MAXN + 5 ];
struct Edge {
int v , w;
};
vector< Edge > Graph[ MAXN + 5 ];
int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ 3 ][ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void Init( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= n ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
for( int i = 1 ; i <= n ; i ++ ) {
f[ 0 ][ i ] = f[ 1 ][ i ] = f[ 2 ][ i ] = 0;
for( int j = i ; j <= n ; j += i ) {
f[ 0 ][ i ] = ( f[ 0 ][ i ] + A / j ) % Mod;
f[ 1 ][ i ] = ( f[ 1 ][ i ] + B / j ) % Mod;
f[ 2 ][ i ] = ( f[ 2 ][ i ] + C / j ) % Mod;
}
}
}
int chk( long long x ) {
return ( x % Mod + Mod ) % Mod;
}
int Calc( int u , int v , int w ) {
return chk( 1ll * f[ 0 ][ u ] * f[ 1 ][ v ] % Mod * f[ 2 ][ w ] % Mod );
}
int Gcd( int a , int b ) {
return !b ? a : Gcd( b , a % b );
}
int Solve( ) {
int Ans = 0;
for( int i = 1 ; i <= m ; i ++ )
Ans = ( Ans + chk( mu[ i ] * mu[ i ] * mu[ i ] * Calc( i , i , i ) ) ) % Mod;
cnt = 0;
for( int i = 1 ; i <= n ; i ++ ) Deg[ i ] = 0;
for( int d = 1 ; d <= n ; d ++ )
for( int i = 1 ; i <= n / d ; i ++ )
for( int j = i + 1 ; j <= n / i / d ; j ++ ) {
int u = i * d , v = j * d , l = i * j * d;
if( Gcd( i , j ) != 1 || !mu[ u ] || !mu[ v ] ) continue;
Ans = ( Ans + chk( mu[ u ] * mu[ u ] * mu[ v ] * chk( 1ll * Calc( u , l , l ) + Calc( l , u , l ) + Calc( l , l , u ) ) ) ) % Mod;
Ans = ( Ans + chk( mu[ u ] * mu[ v ] * mu[ v ] * chk( 1ll * Calc( v , l , l ) + Calc( l , v , l ) + Calc( l , l , v ) ) ) ) % Mod;
E[ ++ cnt ] = { u , v , l };
}
for( int i = 1 ; i <= n ; i ++ ) Graph[ i ].clear( );
for( int i = cnt , u , v , w ; i >= 1 ; i -- ) {
u = E[ i ].u , v = E[ i ].v , w = E[ i ].w;
if( Deg[ u ] < Deg[ v ] || ( Deg[ u ] == Deg[ v ] && u < v ) )
Graph[ u ].push_back( { v , w } );
else
Graph[ v ].push_back( { u , w } );
}
for( int u = 0 ; u <= n ; u ++ ) {
if( !mu[ u ] ) continue;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) vt[ Graph[ u ][ i ].v ] = Graph[ u ][ i ].w;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ].v , uw = Graph[ u ][ i ].w;
if( !mu[ v ] ) continue;
for( int j = 0 ; j < Graph[ v ].size( ) ; j ++ ) {
int w = Graph[ v ][ j ].v , vw = Graph[ v ][ j ].w;
if( !mu[ w ] ) continue;
if( vt[ w ] ) {
int ww = vt[ w ];
Ans = ( Ans + chk( mu[ u ] * mu[ v ] * mu[ w ] * chk( 1ll * Calc( uw , vw , ww ) + Calc( uw , ww , vw ) + Calc( vw , uw , ww ) + Calc( vw , ww , uw ) + Calc( ww , uw , vw ) + Calc( ww , vw , uw ) ) ) ) % Mod;
}
}
}
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) vt[ Graph[ u ][ i ].v ] = 0;
}
return Ans;
}
int main( ) {
scanf("%d", &t );
while( t -- ) {
scanf("%d %d %d", &A , &B , &C );
n = max( A , max( B , C ) );
m = min( A , min( B , C ) );
Init( );
printf("%d\n", Solve( ) );
}
return 0;
}